package main

import "fmt"

func main() {
	root := &TreeNode{
		Val: 3,
		Left: &TreeNode{
			Val: 9,
		},
		Right: &TreeNode{
			Val: 20,
			Left: &TreeNode{
				Val: 15,
			},
			Right: &TreeNode{
				Val: 7,
			},
		},
	}
	fmt.Println(averageOfLevels(root))
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func averageOfLevels(root *TreeNode) []float64 {
	averges := []float64{}
	q := []*TreeNode{root}
	for len(q) > 0 {
		size := len(q)
		sum := 0.0
		for i := 0; i < size; i++ {
			n := q[0]
			q = q[1:]
			sum += float64(n.Val)

			if n.Left != nil {
				q = append(q, n.Left)
			}

			if n.Right != nil {
				q = append(q, n.Right)
			}
		}
		averges = append(averges, sum/float64(size))
	}
	return averges
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
